This invention relates to methods and apparatus for encoding and decoding data, and to communications systems incorporating such methods and apparatus; in particular, though not exclusively, the invention relates to such methods, apparatus and systems for transmitting data using multi-carrier frequency division multiplexing, such as coded orthogonal frequency division multiplexing (COFDM).
The increasingly widespread use of powerful computer-based equipment and appliances is resulting in rapidly increasing requirements for high-speed, high-capacity communications, based on both wireline and wireless techniques. One way of accommodating this increase is to design communications systems for operation at higher and higher symbol rates. However, an increase in symbol rate typically involves a corresponding decrease in inter-symbol spacing, and this in turn can lead to greater inter-symbol interference (ISI) and consequential errors in symbols as received. In the case of wireline links ISI can arise, for example, from signal reflections at imperfectly matched interfaces between different portions of the communications link. For wireless links a significant source of ISI is multi-path propagation involving signal reflections from objects (such as buildings) in the space traversed by the signals; mobile wireless communications can be especially susceptible to ISI from this source, because movement of a mobile unit using the link can cause continuous and complex variation in the multiple propagation paths extending to the mobile unit.
A technique which is being actively studied and developed to increase communications system capacity and counteract ISI is multi-carrier (or multitone) frequency division multiplex operation, such as COFDM operation. In a COFDM system multiple symbols are transmitted simultaneously, each symbol controlling the modulation (e.g. by phase-shift keying) of a respective one of multiple carrier signals having closely-spaced frequencies. By choosing the carrier-frequency spacing to have an appropriate relationship to the rate at which symbols are transmitted on each carrier, it is possible to ensure that each individual carrier can be demodulated without interference from the carriers adjacent to it (in which case the carriers are said to be orthogonal to one another). The set of symbols transmitted simultaneously on respective carriers during a symbol period (a code word) is chosen to encode a group of data symbols (a data word) and includes redundancy (i.e. the code word has more symbols than the data word); this redundancy is used upon reception for detection of errors in the symbols as received, and, if desired, for correction of those errors.
COFDM systems counteract ISI in part because the transmission of multiple symbols in parallel enables a desired data rate to be attained with a lower symbol rate than would be necessary if a serial system were used to transmit individual symbols in succession. A lower symbol rate implies a longer duration for each symbol and thus a longer period between symbol transitions, which reduces the impact of ISI. The error detection and correction capabilities provided by the inclusion of redundancy enhance the resistance to data corruption, by enabling some errors which occur in received symbols owing to signal fading and other causes to be detected and corrected.
However, present COFDM systems encounter difficulties in obtaining the maximum potential benefit for a particular transmitted signal power, owing to limitations arising from the typical peak-to-mean envelope power ratio (PMEPR) of the actual transmitted signal. Because this signal is effectively the sum of several signals at closely spaced frequencies and with respective phases which change at each symbol transition, the overall signal tends to exhibit transient pronounced peaks separated by substantially longer intervals of much lower though still varying amplitude. The transmitting equipment must be adjusted to reproduce the peaks without clipping or other distortion, so for much of the time, in the intervals between peaks, that equipment is operating at a signal level well below its maximum capability. As a result the geographical range of the equipment is significantly lower than would be expected for its nominal power rating, or alternatively a much more powerful equipment must be provided to cover the desired range and then operated inefficiently.
It is known that this problem can in principle be alleviated by careful selection of the code words which encode the possible data words (for example in xe2x80x98Block coding scheme for reduction of peak to mean envelope power ratio of multicarrier transmission schemesxe2x80x99 by A. E. Jones, T. A. Wilkinson and S. K. Barton, Electronics Letters, Dec. 8, 1994, vol.30, no.25, pp. 2098-2099). However, in selecting code words to reduce the PMEPR it is important also to ensure the code has good error correction properties. Furthermore, implementation of a high-throughput communications system desirably involves the use of long code words and of rapid encoding and decoding procedures; the use of simple look-up tables, though readily implemented, does not lend itself to rapid operation using compact (and low-power, inexpensive) circuitry, especially during decoding, if the number of valid code words to be checked is large, as is typically the case with long code words (e.g. more than about 16 symbols). It is therefore preferable for encoding and decoding operations to be definable in terms of some analytical procedure which for example performs combinatorial logic on the data word or code word symbols to convert one to the other, or at least restricts the size of any look-up table which is used.
An additional difficulty is presented by the sheer quantity of possible code words from which a selection may be made to define a code for use in a typical system. As the number of symbols in a code word increases the number of possible code words increases much faster, even for binary symbols; for symbols having just three (ternary) or four (quaternary) possible values, the number of possible codes available becomes so huge even for quite short code words that a simple exhaustive search through all possible code words is not feasible in a realistic time even just to minimize the PMEPR. Attempting to satisfy error correction and implementational requirements as well merely adds to the difficulty of such a search, especially as it will not even be known whether there actually exists a code word set which is of the desired size and which simultaneously satisfies preferred criteria relating to PMEPR, error detection or correction and ease of encoding and decoding. This difficulty is further exacerbated by the desirability of having a large number of code words available for use in the chosen code, in order to be able to encode a large number of different data words (i.e. data words containing relatively many symbols) and thus attain an acceptably high data transfer rate.
It is known that certain kinds of codes may have some desirable properties. Thus the paper xe2x80x98Synthesis of Power Efficient Multitone Signals with Flat Amplitude Spectrumxe2x80x99 by B. M. Popovixc4x87, IEEE Transactions on Communications, vol.39, no.7, July 1991, pp. 1031-1033 indicates that any binary or polyphase complementary sequence can be used to construct a multitone signal with a crest factor (analogous to PMEPR) less than or equal to 6 dBV. Examples of these sequences have been described, as in the case of binary Golay complementary sequence pairs (xe2x80x98Complementary seriesxe2x80x99 by M. J. E. Golay, IRE Transactions on Information Theory, vol.IT-7, April 1961, pp. 82-87). However, Popovixc4x87""s paper is directed to situations such as multipath fading measurements and multitone jamming, in which a single code word can be used continuously in generating the required signal. Accordingly Popovixc4x87 gives no guidance on how multiple such sequences could be identified just to attain the 6 dBV limit on PMEPR in a practical code for conveying information; and no mention whatsoever is made of the other requirements mentioned above for a code suitable for practical implementation. Indeed Popovixc4x87 states that xe2x80x9cthe construction of multitone signals having minimum peak-to-peak amplitude is an old problem that still has no analytical solutionxe2x80x9d.
It should be noted that Golay complementary sequence pairs and codes defined using them are different from and should not be confused with so-called Golay codes; Golay complementary sequence pairs and Golay codes were first defined, independently of one another, by the same researcher and for that reason alone both are referred to by his name.
It is an object of this invention to provide methods and apparatus for encoding and decoding in which a substantial number of different code words are identifiable in practice, despite the potentially huge search space of possible code words, and which provide a predictable low limit on PMEPR, have specified error detection and correction properties and are feasible for implementation in high-speed circuitry.
According to one aspect of this invention there is provided a method of encoding data words as 2m-symbol code words for transmission using multi-carrier frequency division multiplexing, such as coded orthogonal frequency division multiplexing (COFDM), wherein data words are encoded in accordance with their value and code words selected in complete cosets, for desired peak-to-mean envelope power ratio characteristics of said transmission, from a set of one or more cosets of a linear sub-code of a code having a generator matrix as follows:   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit.
According to another aspect of this invention there is provided a method for transmitting data words as 2m-symbol code words using multi-carrier frequency division multiplexing, such as coded orthogonal frequency division multiplexing (COFDM), comprising the steps of:
encoding each data word in accordance with its value and code words selected in complete cosets, for desired peak-to-mean envelope power ratio characteristics of transmission, from a set of one or more cosets of a linear sub-code of a code having a generator matrix as follows:   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit; and
decoding each code word using an analytical decoder.
According to a further aspect of this invention there is provided a method of encoding data words as 2m-symbol code words for transmission using multi-carrier frequency division multiplexing, such as coded orthogonal frequency division multiplexing (COFDM), wherein m is at least 4 and data words are encoded in accordance with their value and code words comprising a set of one or more complete cosets of a linear sub-code of a code having a generator matrix as follows:   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit.
According to a yet further aspect of this invention there is provided a method of encoding data words as 2m-symbol code words, each code word symbol having 2j different possible values, wherein m is at least 4 and j is at least 3, and data words are encoded in accordance with their value and code words comprising a set of one or more complete cosets of a code having a generator matrix as follows:   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit.
According to another aspect of this invention there is provided a method of encoding data words as 2m-symbol code words for transfer over a communication path, each code word symbol having 2j different possible values, wherein j is a variable positive integer, and data words are encoded in accordance with their value and a code having, for any value of j, code words contained within a set of one or more cosets of a linear sub-code of a code having a generator matrix as follows:   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit.
According to a farther aspect of this invention there is provided a method of identifying a 2m-symbol code word within a set of code words having a generator matrix   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit, and each code word symbol has 2j different possible values where j greater than 1,
wherein coefficients for rows of said matrix are derived by:
applying a plurality of fast Hadamard transforms or equivalents thereof to a 2m-symbol input word; and
combining results of said transforms or their equivalents to identify said code word.
According to another aspect of this invention there is provided a coder for encoding data words as 2m-symbol code words for transmission using multi-carrier frequency division multiplexing, such as coded orthogonal frequency division multiplexing (COFDM), comprising means for receiving data words and for encoding them in accordance with their value and code words selected in complete cosets, for desired peak-to-mean envelope power ratio characteristics of said transmission, from a set of one or more cosets of a linear sub-code of a code having a generator matrix as follows:   "AutoLeftMatch"                                                        (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                        (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                  xe2x80x83                                                xe2x80x83                                    ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                                (                                                (                                      2.0                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                                          (                                                (                                      2.1                    +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                      ⁢                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  m                                            )                        /                          2              m                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                              ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                                      m                    -                    1                                                              )                        /                          2                              m                -                1                                                                                      xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  y                                            )                        /                          2              y                                                                        xe2x80x83                                                xe2x80x83                                                xe2x80x83                                                                          (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  1                                            )                        /                          2              1                                                                                      (                                                (                                                            2.                      ⁢                      z                                        +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                                ⋯                                                    (                                                (                                                            2.                      ⁢                                              (                                                                              2                            m                                                    -                          1                                                )                                                              +                    1                                    )                                xc3x97                                  2                  0                                            )                        /                          2              0                                          
where z has integer values from 0 to 2mxe2x88x921, y has integer values from m to 0, x indicates bitwise multiplication of factors expressed as (m+1)-bit binary numbers, and the result of division is expressed as a single digit.
Circuitry implementing this invention is relatively simple and compact. Thus, for example, identifying code words for use in encoding does not require exhaustive searches (of possibly impractical duration) through enormous numbers of code words, even for relatively long code words. Likewise, decoding does not need enormous look-up tables containing all valid code words that may occur, which would again be impractical for long code words. The simplicity and compactness of practical implementation of the invention, as compared to what has previously been believed to be necessary (e.g. exhaustive searches and large look-up tables) or at the limits of feasibility, illustrate the significant advance which the invention provides.